#pragma once
#include <iostream>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode(pair<K, V> kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
    ,_kv(kv)
  {}
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  int _bf;  //balance factor 平衡因子
  pair<K, V> _kv;
};


template<class K, class V>
class AVLTree 
{
  typedef AVLTreeNode<K, V> Node;
  public:
  AVLTree()
  :_root(nullptr)
  {}

  bool insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else 
      {
        return false;
      }
    }
    cur = new Node(kv);
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
    else if (kv.first > parent->_kv.first)
    {
      parent->_right = cur;
      cur->parent = parent;
    }
    return true;
  }
  private:
  Node* _root;
};
